class Solution {
public:
    unordered_map<int, int> ma;
    unordered_map<int, unordered_map<int, unordered_map<int, unordered_map<int, unordered_map<int, pair<int, int>>>>>> dp;
    int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
        ma[0] = 1;
        int temp = 1;
        for (int i = 1; i <= n; i++)
        {
            temp *= 3;
            ma[i] = temp;
        }
        return dfs(0, 0, 0, introvertsCount, extrovertsCount, n, m);
    }
    int get(int bit, int i)
    {
        return (i / ma[bit]) % 3;
    }
    int set(int bit, int s, int i)
    {
        return s - ma[bit] * get(bit, s) + ma[bit] * i;
    }
    int dfs(int i, int j, int s, int a, int b, int n, int m)
    {
        if (dp[i][j][s][a][b].first) return dp[i][j][s][a][b].second;
        if (i == m) return 0;
        if (j == n) return dfs(i + 1, 0, s, a, b, n, m);
        int ans = dfs(i, j + 1, set(j, s, 0), a, b, n, m), near = 0, pre = 0;
        int up = get(j, s);
        int left = j == 0 ? 0 : get(j - 1, s);
        if (up)
        {
            near += 1;
            pre += up == 1 ? -30 : 20;
        }
        if (left)
        {
            near += 1;
            pre += left == 1 ? -30 : 20;
        }
        if (a) ans = max(ans, dfs(i, j + 1, set(j, s, 1), a - 1, b, n, m) + 120 - near * 30 + pre);
        if (b) ans = max(ans, dfs(i, j + 1, set(j, s, 2), a, b - 1, n, m) + 40 + 20 * near + pre);
        dp[i][j][s][a][b].first = 1;
        return dp[i][j][s][a][b].second = ans;
    }
};